Many modern applications encode data prior to transmission of the data on a network using cyclic error correcting codes such as Reed-Solomon codes. Such codes have the potential to provide powerful error correction capability. For example, a Reed-Solomon code of length n and including n−k check symbols may detect any combination of up to t=n−k erroneous symbols and correct any combination of up to └t/2┘ symbols, where └•┘ denotes the floor function. However, decoder implementations for such codes are expensive in terms of an amount of required logic, e.g., in terms of a required number of adaptive look-up tables (ALUTs), and hence, in terms of a size, monetary cost, and power consumption. For example, a typical Reed-Solomon decoder implementation requires a number of finite-field dividers, p, that scales with the codeword length n. For example, a Reed-Solomon decoder for Reed-Solomon codewords of length n=255 may require 5, 10, 15, or a larger number, of finite-field dividers.
Moreover, many modern applications transmit and receive data over high-speed networks, e.g., optical transport networks (OTNs). Such networks typically introduce data errors at a frequency much lower than an error correction capacity of a corresponding error correction code. For example, an OTN network may use a (239, 255) Reed-Solomon code, i.e., a Reed-Solomon code for which each codeword contains 239 data symbols and 255 total coded symbols. Such a code may correct any combination of up to └t/2┘=└(n−k)/2┘=8 erroneous symbols occurring a received codeword. This is equivalent to the codeword being able to correct approximately a three-percent error rate of symbols in the received codeword. However, actual error rates experienced on OTN networks are in the range of 10−9 to 10−15 errors per symbol. Thus, the typical Reed-Solomon code provides an error correction capability in excess of a required error correction capability (and hence utilizes a decoder having implemented with an excess amount of logic circuitry).
Further, high-speed networks typically require some form of data pipelining to attain a satisfactory decoding output rate. Pipelining typically requires a large amount of duplicative circuitry. Finite-field dividers, in particular, are typically duplicated in decoder implementations for high speed networks and often result in a substantial amount of required logic circuitry.